package 剑指offer;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @author zhangmin
 * @create 2021-11-15 14:03
 *
 * 查找算法-中等
 */
public class day5_04_11_50 {

    /**===========================================================================================================================
     * 剑指 Offer 04. 二维数组中的查找
     * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
     * 请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     * 思路：线性查找，从右上角开始，元素大于target时向左走，小于时向下走
     * */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length==0){
            return false;
        }
        int n=matrix.length,m=matrix[0].length;
        int i=0,j=m-1;
        while (i<n&&j>=0){
            if (matrix[i][j]==target) return true;
            else if (matrix[i][j]<target){
                //向下走，到更大的区域去找
                i++;
            }else if (matrix[i][j]>target){
                //向左走，到跟小的区域
                j--;
            }
        }
        return false;
    }


    /**===========================================================================================================================
     * 剑指 Offer 11. 旋转数组的最小数字
     * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
     * 例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。  
     * 二分查找：可以中间元素与right元素的对比，得知哪一半是递增的，哪一半是存在最小元素的
     * */
    public int minArray(int[] numbers) {
        int left=0,right=numbers.length-1;
        if (numbers.length==1)
            return numbers[0];
        while (left<right){
            int mid=left+(right-left)/2;
            if (numbers[mid]>numbers[right]){
                //左边全部是递增的，在右半部分中包含最小元素
                left=mid+1;
            }else if (numbers[mid]==numbers[left]){
                right--;
            }else {
                //右边是递增的，最小元素在左边
                right=mid;
            }
        }
        return numbers[left];
    }

    /**===========================================================================================================================
     * 剑指 Offer 50. 第一个只出现一次的字符
     * 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
     * */
    public char firstUniqChar(String s) {
        if (s.length()==0) return ' ';
        //map记录每个元素出现的下标，当元素重复出现时，将其标志为-1
        Map<Character,Integer> map=new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char sc=s.charAt(i);
            if (map.containsKey(sc)){
                map.put(sc,-1);
            }else {
                map.put(sc,i);
            }
        }
        int resIndex=s.length();
        for (Map.Entry<Character,Integer> entry:map.entrySet()) {
            Integer ind = entry.getValue();
            if (ind!=-1&&ind<resIndex){
                resIndex=ind;
            }
        }
        return resIndex==s.length()?' ':s.charAt(resIndex);
    }
}
